package T;

import com.sun.source.tree.Tree;

import java.util.Stack;

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }

      //使用递归实现验证二叉树
    private long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null) {
            return true;
        }
        boolean l = isValidBST(root.left);
        if (!l) {
            return false;
        }
        if(prev >= root.val) {
            return false;
        }
        prev = root.val;
        return isValidBST(root.right);
    }

    //使用遍历实现验证二叉树
    public boolean isValidBST2(TreeNode node) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = node;
        long prev = Long.MIN_VALUE;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            }else {
                TreeNode pop = stack.pop();
                if(pop.val <= prev) {
                    return false;
                }
                prev = pop.val;
                p = pop.right;
            }
        }
        return true;
    }

    //使用递归求二叉搜索树的范围和
    public int rangeSum(TreeNode root,int slow, int high) {
        if(root == null) {
            return 0;
        }
        if(root.val < slow) {
            return rangeSum(root.right,slow,high);
        }
        if(root.val > high) {
            return rangeSum(root.left,slow,high);
        }
        return root.val + rangeSum(root.left,slow,high) + rangeSum(root.right,slow,high);
    }

    //使用非递归求二叉搜索树的范围和
    public int rangeSum2(TreeNode root,int slow,int high) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        int sum = 0;
        while(p != null || !stack.isEmpty()) {
            if(p != null) {
                stack.push(p);
                p = p.left;
            }else {
                TreeNode pop = stack.pop();
                if(pop.val > high) {
                    break;
                }
                if(pop.val >= slow) {
                    sum += pop.val;
                }
                p = pop.right;
            }
        }
        return sum;
    }

    //根据前序遍历的结果建树
    public TreeNode bstFromPreorder(int[] preorder) {
        TreeNode root = new TreeNode(preorder[0]);
        for(int i = 1; i < preorder.length; i++) {
            TreeNode p = new TreeNode(preorder[i]);
            insert(root,p);
        }
        return root;

    }
    //使用非递归的方式
    public void insert(TreeNode root, TreeNode node) {
        TreeNode p = root;
        TreeNode parent = null;
        while(p != null) {
            if(p.val < node.val) {
                parent = p;
                p = p.right;
            }else if(p.val > node.val) {
                parent = p;
                p = p.left;
            }
        }
        if(parent.val > node.val) {
            parent.left = node;
        }else {
            parent.right = node;
        }
    }
    //使用递归的方式
    public  TreeNode insert(TreeNode node, int val) {
        if (node == null) {
            return new TreeNode(val);
        }
        if (node.val > val) {
            node.left = insert(node.left,val);
        }else {
            node.right = insert(node.right,val);
        }
        return node;
    }

    //二叉搜索树的最近祖宗
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode a = root;
        while(p.val < a.val && q.val < a.val || p.val > a.val && q.val > a.val) {
            if(p.val < a.val) {
                a = a.left;
            }else {
                a = a.right;
            }
        }
        return a;
    }

}

